package Tree;

import java.util.HashMap;
import java.util.Map;

/**
 * 根据一棵树的前序遍历与中序遍历构造二叉树。
 *
 * 注意:
 * 你可以假设树中没有重复的元素。
 *
 * 例如，给出
 *
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 *
 * preorder = [3,9,20,15,7]
 * inorder = [9,3,15,20,7]
 * 首先根据 preorder 找到根节点是 3
 *
 * 然后根据根节点将 inorder 分成左子树和右子树
 * 左子树
 * inorder [9]
 *
 * 右子树
 * inorder [15,20,7]
 *
 * 把相应的前序遍历的数组也加进来
 * 左子树
 * preorder[9]
 * inorder [9]
 *
 * 右子树
 * preorder[20 15 7]
 * inorder [15,20,7]
 *
 * 现在我们只需要构造左子树和右子树即可，成功把大问题化成了小问题
 * 然后重复上边的步骤继续划分，直到 preorder 和 inorder 都为空，返回 null 即可
 *
 */
public class L105_前序后续确定二叉树 {

    public TreeNode buildTreeMap(int[] preorder, int[] inorder){
        Map<Integer, Integer> inMap = new HashMap<>();
        for(int i=0; i < inorder.length; i++){
            inMap.put(inorder[i], i);
        }
        return buildTreeMap_rec(preorder, 0, preorder.length, inorder, 0, inorder.length, inMap);
    }
    private TreeNode buildTreeMap_rec(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end, Map<Integer, Integer> inMap){
        if(p_start == p_end){
            return null;
        }
        TreeNode root = new TreeNode(preorder[p_start]);
        int i_root_index = inMap.get(preorder[p_start]);
        int leftNum = i_root_index - i_start;//算出中序，根节点到左节点的距离，在这里面产出左节点

        root.left = buildTreeMap_rec(preorder,
                p_start + 1, p_start + leftNum + 1,//通过中序的就能确定
                    inorder, i_start, i_root_index, inMap
                );
        root.right = buildTreeMap_rec(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end, inMap);
        return root;
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree_rec(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }
    private TreeNode  buildTree_rec(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end){
        if(p_start == p_end){
            return null;
        }
        //前序遍历，可以立马确定节点
        TreeNode root = new TreeNode(preorder[p_start]);

        //开始找这个节点的位置，然后，给划分成左右节点，进行递归即可
        int i_root_index = 0;
        //在中序种，找到根节点位置
        for(int i=i_start; i < i_end; i++){
            if(inorder[i] == preorder[p_start]){
                i_root_index = i;
                break;
            }
        }
        //当前节点 往右到中序节点 多少距离，这个距离都是左边节点的
        int leftNum = i_root_index - i_start;
        //确定左节点的范围，在 前序遍历的右边，以及 中序里获得的距离差
        root.left = buildTree_rec(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index );
        root.right = buildTree_rec(preorder, p_start + leftNum +1, p_end, inorder, i_root_index + 1, i_end);

        return root;
    }

    public static void main(String[] args){
        L105_前序后续确定二叉树 l = new L105_前序后续确定二叉树();
        int[] p = new int[]{3,9,20,15,7};
        int[] i = new int[]{9,3,15,20,7};
        l.buildTree(p,i);
    }

}
